1. Field of the Invention
The present invention is directed generally to a system and method of cryptography and, more particularly, to a system and method of cryptography that deterministically generates block substitution tables which meet a given standard of nonlinearity.
2. Description of the Background
Block substitution is a method used to encrypt a clear text message which is in the form of a sequence of binary numbers. There is considerable interest in the cryptographic community in block substitution tables or S-boxes which are highly nonlinear in some sense. This is particularly important in Feistel-type systems, of which DES is a prime example. In such systems, the key is used to interact with the clear text data and the substitution tables serve as barriers to limit access to the key by comparing clear text with cipher text data. The primary tools of cryptanalysis against Feistel-type systems are differential and linear cryptanalysis. The principal foil against these is nonlinearity as typically measured by L1 and L4 norms using the Walsh-Fourier transform. Emphasis on these measures is often so great that weakness in other measures is accepted in order to achieve high scores in nonlinearity. In particular, highly nonlinear tables which are weak in complexity and characterized by short cycles and multiple fixed points may be used. However, in most Feistel-type systems the tables are permanently fixed and publicly known so that these flaws are considered acceptable. Another consideration is that these highly nonlinear tables are generally found by searching and their properties are determined empirically by testing rather than relying on underlying mathematical theory.
Instead of a Feistel-type system, one can also use throw-away, secret tables for one-time use and use the cryptographic keys to generate tables, to generate inter-round mixing patterns, and effectively, to determine the algorithm rather than to merely mingle with the data. Excellent cryptographic strength can be achieved by numerous measures including cycle structure, avalanching, bit independence, perfect balance, and nonlinearity, albeit, not necessarily with the highest possible L1 and L4 norms.
The prior methods have the disadvantages that they are not flexible enough to meet users' needs and the substitution tables are developed by trial and error. Thus, there is a need for a cryptographic method that emphasizes designing to the customers' needs rather than offering take-it-or-leave-it products of fixed characteristics. There is also a need for a cryptographic method that can be designed to cost, designed to strength, and designed to speed, both for data rates and table generation and designed for nonlinearity. There is also a need for a cryptographic method that deterministically generates tables that do not have to be exhaustively tested.